/*
 * @lc app=leetcode.cn id=115 lang=javascript
 *
 * [115] 不同的子序列
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
  const sLen = s.length;
  const tLen = t.length;
  // dp数组，需要有base case，所以都要加1个
  const dp = new Array(sLen + 1).fill(0).map((_) => new Array(tLen + 1).fill(0));

  for (let i = 0; i <= sLen; i++) {
    for (let j = 0; j <= tLen; j++) {
      if (j === 0) {
        dp[i][j] = 1;
      } else if (i === 0) {
        dp[i][j] = 0;
      } else {
        if (s[i - 1] === t[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j];
        }
      }
    }
  }

  return dp[sLen][tLen];
};
// @lc code=end
